package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.*;


public class GreedyRandomizedAdaptiveSearch extends LocalSearch3 {

    private final int nodeNum;

    public GreedyRandomizedAdaptiveSearch(Problem problem) {
        super(problem);
        this.nodeNum = problem.getNodeNum();
    }

    @Override
    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("greedy randomized search init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("greedy randomized search final", finalSolution);
        CheckUtils.check(finalSolution, distance);
    }

    @Override
    public Solution initial() {
        return createRestrictedCandidate();
    }

    /** RCL + local search*/
    @Override
    public Solution improve(Solution solution) {
        Solution bestSolution = solution.copy();
        int iterations = 100;
        int rclNum = 25;
        int iter = 0;
        while (iter < iterations) {
            List<Solution> rcl = new ArrayList<>();// Restricted Candidate List (RCL)
            for (int i = 0; i < rclNum; i++) {
                rcl.add(createRestrictedCandidate());
            }
            // multi-start
            int candidate = random.nextInt(rcl.size() - 1) + 1;
            Solution currentSolution = localSearch(rcl.get(candidate));
            // 如果局部搜索不发生变化，则退出；否则一直探索下去
            while (currentSolution != rcl.get(candidate)) {
                rcl.set(candidate, currentSolution);
                currentSolution = localSearch(rcl.get(candidate));
            }

            if (currentSolution.getCost() < bestSolution.getCost()) {
                bestSolution = currentSolution.copy();
            }
            iter++;
            System.out.format("第%d次迭代最优解：%d\n", iter, bestSolution.getCost());
        }
        return bestSolution;
    }

    private Solution createRestrictedCandidate() {
        int i = 0;
        List<Integer> solution = new ArrayList<>();
        solution.add(i);
        while (solution.size() < nodeNum) {
            int[] next = new int[nodeNum];
            for (int k = 0; k < nodeNum; k++) {
                next[k] = distance[i][k];
            }
            int j = selectNextNeighborhood(next, solution);
            solution.add(j);
            i = j;
        }
        return new Solution(solution, calculateFitness(solution));
    }

    private int selectNextNeighborhood(int[] distance, List<Integer> solution) {
        List<Integer> candidate = new ArrayList<>();
        for (int i = 0; i < distance.length; i++) {
            if (!solution.contains(i)) {
                candidate.add(distance[i]);
            }
        }

        double alpha = 0.5;//alpha=0纯贪心，alpha=1纯随机
        int min = Collections.min(candidate);
        int max = Collections.max(candidate);
        double bound = min + alpha * (max - min);
        List<Integer> rcl = new ArrayList<>();
        for (int i = 0; i < distance.length; i++) {
            if (!solution.contains(i)) {
                if (distance[i] <= bound) {
                    rcl.add(i);
                }
            }
        }
        //随机从rcl中选择一个
        int rnd = random.nextInt(rcl.size());
        return rcl.get(rnd);
    }


}
